Within the past decade, the advent of world-wide electronic communications systems has enhanced the way in which people can send and receive information. In particular, the capabilities of real-time video and audio systems have greatly improved in recent years. In order to provide services such as video-on-demand and videoconferencing to subscribers, an enormous amount of network bandwidth is required. In fact, network bandwidth is often the main inhibitor to the effectiveness of such systems.
In order to overcome the constraints imposed by networks, compression systems have emerged. These systems reduce the amount of video and audio data which must be transmitted by removing redundancy in the picture sequence. At the receiving end, the picture sequence is uncompressed and may be displayed in real-time.
One example of an emerging video compression standard is the Moving Picture Experts Group ("MPEG-2") standard. Within the MPEG-2 standard, video compression is defined both within a given picture and between pictures. Video compression within a picture is accomplished by conversion of the digital image from the time domain to the frequency domain by a discrete cosine transform, quantization, and variable length coding, such as Huffman coding. Video compression between pictures is accomplished via a process referred to as motion estimation and compensation, in which a motion vector plus difference data is used to describe the translation of a set of picture elements (pels) from one picture to another.
The ISO MPEG-2 standard specifies only the syntax of bitstream and semantics of the decoding process. The choice of coding parameters and trade-offs in performance versus complexity is left to the encoder developers. Since MPEG-2 encoder development is complex and expensive, an encoder solution that is flexible for different applications and that can expand as the customer's needs evolve, that is, a scalable encoder, is desirable.
One computation intensive aspect of MPEG-2 encoding is motion estimation and compensation. This involves such computation intensive steps as memory fetches and stores, searches, comparisons, matches, and motion vector calculations. A need exists for a fast search for a best-match macroblock in a search window on downsampled full pixel values.
A further need exists for a fast search on non-downsampled reconstructed data around the best match macroblock to find a more precise match to use for motion vector coding.